/*
 * ICS 211
 * Fall 2011
 * Homework 5
 * @author Ryne Okimoto
 * 
 * LinkedList class.  Creates a linked list and performs
 * operations on that list.
 */

package dlldynamicset;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;

// Old code implemented java.lang.iterable<E>

public class DLLDynamicSet <E, K extends Comparable<K>> implements java.lang.Iterable<E>
{	
	// Data for DLLDynamicSet
	private DLLNode<E, K> head;
	private DLLNode<E, K> tail;
	private int size;
	
	/**
	*	Default constructor
	*	Initializes an empty list.
	*/
	public DLLDynamicSet()
	{
		head = null;
		tail = null;
		size = 0;
	}
	
	private static class DLLNode<E, K extends Comparable<K>> implements Comparable<DLLNode<E, K>>{
		
		private E data;
		// Need to implement key
		private K key;
		private DLLNode<E, K> next;
		private DLLNode<E, K> previous;
		
		
		/**
		*	Constructor to create a node with a given datatype
		*/
		public DLLNode(E datavalue, K keyvalue){
			data = datavalue;
			// Initialize key
			key = keyvalue;
			next = null;
			previous = null;
		}
		
		public DLLNode
			(E datavalue, K keyvalue, DLLNode<E, K> nextNode, DLLNode<E, K> previousNode)
		{
			data = datavalue;
			// Initialize key
			key = keyvalue;
			next = nextNode;
			previous = previousNode;
		}
		
		public DLLNode<E, K> getNext()
		{
			return next;
		}
		
		public DLLNode<E, K> getPrevious()
		{
			return previous;
		}
		
		public void setNext(DLLNode<E, K> node)
		{
			next = node;
		}
		
		public void setPrevious(DLLNode<E, K> node)
		{
			previous = node;
		}
		
		public K getKey()
		{
			return key;
		}
		
		
		public E getData()
		{
			return data;
		}
		
		public String toString()
		{
			return key.toString();
		}
		
		public int compareTo(DLLNode<E, K> anotherRecord)
		{
			return this.key.compareTo(anotherRecord.getKey());
		}
	} // class DLLNode
	
	
	/**
	 * Class - SetIterator
	 * Description - Iterator for the superclass
	 * @author Ryne
	 *
	 */
	public class SetIterator implements java.util.Iterator<E>{
		
		private DLLNode<E, K> currentNode;
		
		private SetIterator(){
			currentNode = head;
		}
		
		public boolean hasNext(){
			return currentNode != null;
		}
		
		public E next(){
			if(hasNext()){
				E result = currentNode.getData();
			
				currentNode = currentNode.getNext();
				
				return result;
			}
			throw new NoSuchElementException();
		}
		
		public void remove(){
			throw new UnsupportedOperationException();
		}
	}
	
	public Iterator<E> iterator(){
		return new SetIterator();
	}
	
	/**
	 * Method - insertObject
	 * Description - Inserts an object and its key into the collection
	 * @param data
	 * @param key
	 * @return void
	 */
	public void insertObject(E data, K key){
		insert(new DLLNode<E, K>(data, key));
	}
	
	/**
	*	Method to insert an element into the list
	*	Pre: The list is sorted
	*	Post: The list is sorted
	*
	*/
	private void insert(DLLNode<E, K> nodeToAdd)
	{
		// Add to empty list
		if(head == null)
		{
			head = nodeToAdd;
			tail = nodeToAdd;
		}
		else
		{
			DLLNode<E, K> tempNode = head;
			while(tempNode.getNext() != null && nodeToAdd.compareTo(tempNode) > 0)
			{
				tempNode = tempNode.getNext();
			}
			
			// Add at front of list containing elements
			if(tempNode == head)
			{
				tempNode.setPrevious(nodeToAdd);
				nodeToAdd.setNext(tempNode);
				
				head = nodeToAdd;
			}
			
			// Add at end of list containing elements
			else if(tempNode == tail)
			{
				tempNode.setNext(nodeToAdd);
				nodeToAdd.setPrevious(tempNode);
				
				tail = nodeToAdd;
			}
			
			// Add to somewhere within the list
			else
			{
				// Connect added node
				nodeToAdd.setNext(tempNode);
				nodeToAdd.setPrevious(tempNode.getPrevious());
				
				// Change references for tempNode
				tempNode.getPrevious().setNext(nodeToAdd);
				tempNode.setPrevious(nodeToAdd);
			}
		} 
		
		size++;
	}
	
	/**
	 * Method - deleteKey
	 * Description - Searches the collection for a given key and deletes the first 
	 *               matching key.
	 * @param key
	 * @return boolean
	 */
	public boolean deleteKey(K key){
		boolean isDeleted = false;
		DLLNode<E, K> searchResult = search(key);
		
		if(searchResult != null){
			delete(searchResult);
			isDeleted = true;
		}
		
		return isDeleted;
	}
	
	/**
	*	Method to delete an element from the list if it exists
	*	Pre: The list is sorted
	*	Post: The list is sorted
	*/
	private void delete(DLLNode<E, K> nodeToDelete)
	{
		DLLNode<E, K> searchResult = null;
		
		if(head != null)
		{
			if(nodeToDelete.compareTo(head) == 0)
			{
				// Delete from list with one item
				if(head == tail)
				{
					head = null;
					tail = null;
				}
				// Delete from head of list
				else
				{
					head = head.getNext();
					head.setPrevious(null);
				}
			}
			// Delete from tail of list
			else if(nodeToDelete.compareTo(tail) == 0)
			{
				tail = tail.getPrevious();
				tail.setNext(null);
			}
			// Delete from within list
			else
			{
				searchResult = search(nodeToDelete.getKey());
				if(searchResult != null)
				{
					searchResult.getPrevious().setNext(searchResult.getNext());
					searchResult.getNext().setPrevious(searchResult.getPrevious());
				}
			}	
		}
	}
	
	public int size()
	{
		return size;
	}
	
	
	public boolean searchForKey(K key){
		if(search(key) ==  null){
			return false;
		}
		return true;
	}
	
	private DLLNode<E, K> search(K key)
	{
		DLLNode<E, K> searchResult = head;
		
		while((searchResult != null) && (searchResult.getKey().compareTo(key) != 0))
		{
			searchResult = searchResult.getNext();
		}
		
		return searchResult;
	}
	
	public DLLNode<E, K> minimum()
	{
		return head;
	}
	
	public DLLNode<E, K> maximum()
	{
		return tail;
	}
	
	public DLLNode<E, K> successor(DLLNode<E, K> node)
	{
		return node.getNext();
	}
	
	public DLLNode<E, K> predecessor(DLLNode<E, K> node)
	{
		return node.getPrevious();
	}
	
	public String toString()
	{
		DLLNode<E, K> printedNode = head;
		String printedString = null;
		
		while(printedNode != null)
		{
			if(printedString == null)
			{
				printedString = printedNode.toString() + "\n";
			}
			else
			{
				printedString = printedString.concat(printedNode.toString() + "\n");
			}
			
			printedNode = printedNode.getNext();
		}
		
		return printedString;
	}
	
	
	/**
	 * Unit tester for the class
	 * @param none
	 */
	public static void main(String[] args) 
	{
		
		char command = '0';
		DLLDynamicSet<String, String> testList = new DLLDynamicSet<String, String>();
		Scanner readInput = new Scanner(System.in);
		String key = null;
		String data = null;
		DLLNode<String, String> searchResult = null;
		
		readInput.useDelimiter("\n");
		
		System.out.println("Unit test for DLLDynamicSet and DLLNode\n");
		
		while(command != 'q')
		{
			System.out.print(
					"\n\n\n******   Command Menu   ******\n\n" +
					"1) Insert item\n" +
					"2) Delete item\n" +
					"3) Get size of list\n" +
					"4) Get minimum\n" +
					"5) Get maximum\n" +
					"6) Find successor\n" +
					"7) Find predecessor\n" +
					"8) Print keys\n" +
					"9) Read data from file\n" +
					"q) Quit\n\n" +
					": "
					);
			command = readInput.next().toCharArray()[0];
			
			switch(command)
			{
			case '1':
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test insert   ******" + "\n" +
						"Enter node data: "
						);
				data = readInput.next();
				
				System.out.print("Enter node key: ");
				key = readInput.next();
				
				testList.insert(new DLLNode<String, String>(data, key, null, null));
				
				break;
			case '2':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test delete   ******" + "\n" +
						"Enter key: "
						);
				key = readInput.next();
				
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					testList.delete(searchResult);
					System.out.println("Key deleted.");
				}
				else
				{
					System.out.println("Key not found.");
				}
				
				break;
			case '3':
				System.out.print("\n\n******   Size of list ******\n" +
						"Number of elements: " + testList.size()
						);
				break;
			case '4':
				System.out.print("\n\n******   Get minimum   ******\n" +
						"Minimum key: " + testList.minimum()
						);
				break;
			case '5':
				System.out.print("\n\n******   Get maximum   ******\n" +
						"Maximum key: " + testList.maximum()
						);
				break;
			case '6':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find successor   ******\n" +
						"Enter key: "
						);
				
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Successor: " + testList.successor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				
				break;
			case '7': 
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find predecessor   ******\n" +
						"Enter key: "
						);
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Predecessor: " + testList.successor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				break;
			case '8':
				System.out.println(testList);
				break;
			case '9':
				System.out.print("\n\n******   Read data from file   ******" + "\n" +
						"Enter a file name: "
						);
				//ReadStringFile fileToRead = new ReadStringFile(readInput.next());
				/*
				while(fileToRead.hasLine())
				{
					keyAndData = fileToRead.readLine();
					testList.insert(new DLLNode<String, String>(keyAndData, keyAndData));
				}
				*/
				break;
			case 'q':
				System.out.println("Exiting program...");
				break;
			default:
				System.out.println("Please choose a valid option.");
			}
			
		}
		
		
	}
}
